This application is related to U.S. patent application Ser. No. 629,349 of Lefsky, filed July 10, 1984, now U.S. Pat. No. 4,750,154 and incorporates that application herein by reference.
This invention relates to data processing apparatus having a central processor, a memory and a write buffer associated with said memory. More particularly, the invention relates to apparatus and methods for improving the transfer of data between processors or other input/output devices and memory or data storage devices.
High speed computer systems employ memory devices to store data generated or modified by a central processing unit (CPU). The transfer of the data from the CPU to the memory is typically referred to as a "write operation" or a "write." The transfer of data from the memory to the CPU is referred to as a "read operation" or a "read." In most computer systems, the memory bus, across which multiple bit data words are transferred in parallel, is the same width as the buses employed by the processor to manipulate or generate data. Typically, processors operate on 16 bit or 32 bit data words.
When a processor performs successive write instructions, performance is compromised because the time required to transfer data to memory is much greater than the processor's internal data manipulation cycle time. The processor must wait until each write instruction has been performed before continuing operations.
The conventional method for reducing such Performance costs during the transfer of data from a processor to memory has been to employ a first-in, first-out (FIFO) buffer to store data strings until the buffer is full or a break in processing operations occurs, at which time the buffer entries are unloaded serially into the memory. Such a FIFO buffer is known as a "write buffer".
Write buffers have accordingly been used in high speed computer systems to smooth the flow of data between the central processor and the memory during write operations, as well as to keep the data paths between the two free for read operations.
An associative, "smart" write buffer arrangement is disclosed in U.S. patent application Ser. No. 629,349 of Lefsky, filed July 10, 1984. In the write buffer system disclosed therein, data is accepted by the write buffer as it arrives from the central processor where it is saved temporarily. If subsequent data reaching the write buffer is destined for a memory location which is contiguous to that for which the previously stored data is destined, the two pieces of data are merged inside the write buffer. The merged data is thereafter transferred to memory in a single write operation. Thus only one write operation need be seen by the memory for the two data words, resulting in a significant improvement in speed for the system, provided that wider data words can be written from the write buffer to the memory than can be written from the CPU to the write buffer.
Generally, in such systems it is desirable to save a data word as long as possible in the write buffer, with the expectation that a subsequently received data word will allow such merging to occur. Preferrably, this saving of data would continue until the length of the contiguous data equals the maximum length word the memory can accept at one time.
The value of a write buffer is dependent upon its depth as well as the type of operation being performed by the processor. Where each write operation addresses a separate location in the buffer, the data words to be written to memory must be unloaded individually. Hence, a series of write instructions can quickly fill even a large write buffer, and a typical write buffer has only four locations. When the buffer is full it cannot accept any more data from the central processor, delaying the processor and causing the problem the buffer was designed to relieve. The procedure used to extract data from the write buffer must accordingly seek to balance the two opposing requirements of maximizing buffer residence time while avoiding buffer filling.
In a FIFO write buffer, data is entered into the buffer in a clear sequential format. In a "smart" write buffer such as that disclosed in U.S. patent application Ser. No. 629,349, data is not maintained in the sequence in which it entered. Instead, data strings are merged whenever possible. There is accordingly no information about the residence time of data in the buffer. Consequently, some data may be resident in the buffer for relatively long time periods, thereby compromising the ability of the system to efficiently write to memory.
Accordingly, it is an object of the invention to provide data processing apparatus having a write buffer from which data strings are selected for writing to memory on the basis of each candidate's residence time and likelihood of merging with data coming from a future CPU write operation.